#include <stdlib.h>
#include <unistd.h>
#include <math.h>
#include <stdio.h>
#include "graphe.h"
#include "liste.h"

#define GSIZE(o) (sizeof(int) + sizeof(t_som)*(o))
#define room(g,s) (g->lsom[(s)])
#define succ(g,s) (room(g,s)->succ)
#define pred(g,s) (room(g,s)->pred)
#define next(p) ((p)=(p)->next)
/*int cout (t_graph g, int src, int dest)
{

}*/
t_graph create_graph(int order)
{
  t_graph	        g;
  int		        i;
  g = malloc(GSIZE(order));
  g->order = order;
  for (i=0; i<order; i++)
    {
      room(g,i) = malloc(sizeof(struct s_som));
      room(g,i)->som = i;
      room(g,i)->cost = 0;
      succ(g,i) = pred(g,i) = NULL;
    }
  return g;
}
 
void add_somCost (t_graph g, int som, float cost)
{
    t_som ps =      NULL;
    if ((ps = room(g,som)))
        ps->cost = cost;
}

void add_arc(t_graph g, int s, int d, float c)
{
  t_adj		pa;
  pa = malloc(sizeof(struct s_adj));
  pa->cost = c;
  pa->vsom = d;
  pa->next = succ(g,s);
  succ(g,s) = pa;
  pa = malloc(sizeof(struct s_adj));
  pa->cost = c;
  pa->vsom = s;
  pa->next = pred(g,d);
  pred(g,d) = pa;
}

int has_succ (t_graph g, t_som ps, int s)
{
    t_adj           pa = NULL;
    pa = succ(g,ps->som);
    while (pa)
    {
        if (pa->vsom == s)
        {
            printf("%g\n", pa->cost + ps->cost);
            return pa->cost + ps->cost;
        }
        next(pa);
    }    
    return 0;
}

int parcours (t_graph g, int *i, float *vies)
{
    t_som           ps = NULL;
    int             cpt = 0;
    float           cout;
    ps = room(g, *i);
    do
    {
        printf ("check de %d (%d) a %d\n", ps->som, i[cpt], i[cpt+1]);
        if (!(cout = has_succ (g, ps, i[cpt+1])))
        {
            printf("%g\n", cout);
            return 0;
        }
        printf("%g\n", cout);
        *vies -= cout;
        if (*vies < 1)
            return -1;
        cpt++;
        ps = room (g, i[cpt]);
    } while (i[cpt+1]);
    cpt++;
    return cpt;
}

void dijkstra (t_graph g, int src, int *pere, float *dist)
{
    t_som           ps = NULL;
    t_adj           pa = NULL;
    int             sa;
    t_liste         ouverts = NULL;
    pere[0] = -1;
    for (sa = 1; sa < g->order; sa++)
    {
        pere[sa] = 0;
        dist[sa] = INFINITY;
    }
    pere[src] = src;
    dist[src] = 0;
    ouverts = ajouter (room(g,src), NULL);
    do
    {
        ps = take_min (&ouverts);
        src = ps->som;
        pa = succ(g, src);
        while (pa)
        {
            sa = pa->vsom;
            if (dist[sa] > dist[src] + pa->cost + ps->cost)
            {
                dist[sa] = dist[src] + pa->cost + ps->cost;
                pere[sa] = src;
                if (!belongto(room(g, pa->vsom), ouverts))
                {
                    ouverts = ajouter (room(g, pa->vsom), ouverts);
                }
            }
            next(pa);
        }
    } while (!is_empty(ouverts));
}


